Search results for "Modular decomposition"
showing 4 items of 4 documents
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
Algorithms on Graphs
1988
In this chapter we shall develop some basic algorithms for directed graphs and relations which will be of use in later chapters, where the efficient construction of parsers is considered. The constructions needed can be expressed as the computing of certain “relational expressions”. These are expressions whose operands are relations and whose operators are chosen from among multiplication, closure, union and inverse. For this purpose we need to develop an algorithm for computing the closure of a relation. In view of the nature of our applications, the most appropriate way to do this is by a depth-first traversal of the graph that corresponds to the given relation. Other ways of computing th…
On a Quantitative Measure for Modularity Based on Information Theory
2005
The concept of modularity appears to be crucial for many questions in the field of Artificial Life research. However, there have not been many quantitative measures for modularity that are both general and viable. In this paper we introduce a measure for modularity based on information theory. Due to the generality of the information theory formalism, this measure can be applied to various problems and models; some connections to other formalisms are presented.
Space-by-Time Modular Decomposition Effectively Describes Whole-Body Muscle Activity During Upright Reaching in Various Directions
2017
The modular control hypothesis suggests that motor commands are built from precoded modules whose specific combined recruitment can allow the performance of virtually any motor task. Despite considerable experimental support, this hypothesis remains tentative as classical findings of reduced dimensionality in muscle activity may also result from other constraints (biomechanical couplings, data averaging or low dimensionality of motor tasks). Here we assessed the effectiveness of modularity in describing muscle activity in a comprehensive experiment comprising 72 distinct point-to-point whole-body movements during which the activity of 30 muscles was recorded. To identify invariant modules o…